/**
 * 1457. 二叉树中的伪回文路径
 * https://leetcode-cn.com/problems/pseudo-palindromic-paths-in-a-binary-tree/
 */
public class Solutions_1457 {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(2);
        root.left = new TreeNode(3);
        root.left.left = new TreeNode(3);
        root.left.right = new TreeNode(1);
        root.right = new TreeNode(1);
        root.right.right = new TreeNode(1);

        int result = pseudoPalindromicPaths(root);
        System.out.println(result);
    }

    // 使用二进制记录出现次数
    private static int nums = 0;
    // 从根节点到叶子节点，其中的元素能够构成回文串的数量
    private static int res = 0;
    /**
     * 解法二：位运算（异或）方式（3ms）
     */
    public static int pseudoPalindromicPaths(TreeNode root) {
        if (root == null) {
            return res;
        }
        nums ^= 1 << root.val;
        // 使用异或操作，标记该元素出现一次
        if (root.left == null && root.right == null) {
            // 判断记录下的数字，是否能够构成回文串
            if (nums == 0 || (nums & nums - 1) == 0) {
                // 要么为 0，说明路径中全部是只出现两次的数字，或者二进制位中只有一个 1，即只有一个只出现一次的数字
                res ++;
            }
        }
        if (root.left != null) {
            pseudoPalindromicPaths(root.left);
        }
        if (root.right != null) {
            pseudoPalindromicPaths(root.right);
        }
        // 该节点下的子树遍历完后，使用异或操作，该元素出现次数减 1
        nums ^= 1 << root.val;
        return res;
    }

    /**
     * 解法一：数组记录元素出现次数（13ms）
     */
    // arr[3] = 2，元素在 3 在路径中出现 2 次
    private static int[] arr = new int[10];

    public static int pseudoPalindromicPaths2(TreeNode root) {
        if (root == null) {
            return res;
        }
        // 对递归到的元素，次数加 1
        arr[root.val] ++;
        if (root.left == null && root.right == null) {
            // 判断记录下的数字，是否能够构成回文串
            res += isPalindromic(arr) ? 1 : 0;
        }
        pseudoPalindromicPaths(root.left);
        pseudoPalindromicPaths(root.right);
        // 左右子树都遍历完了，当前节点记录的次数减 1
        arr[root.val] --;
        return res;
    }

    /**
     * arr 中的元素，能否构成回文串
     * @param arr
     * @return true：能，false：不能
     */
    public static boolean isPalindromic(int[] arr) {
        int count = 0;
        for (int i : arr) {
            count += i % 2 == 1 ? 1 : 0;
        }
        // 即出现奇数次的元素不超过 1 个
        return count <= 1;
    }
}
